Search for: All records

Deploying nanoscopic particles and robots in the human body promises increasingly selective drug delivery with fewer side effects. We consider the problem of a homogeneous swarm of nanobots locating a singular cancerous region and treating it by releasing some onboard payload of drugs once at the site. At nanoscale, the computation, communication, sensing, and locomotion capabilities of individual agents are extremely limited, noisy, and/or nonexistent. We present a general model to formally describe the individual and collective behaviour of agents in a colloidal environment, such as the bloodstream, for the problem of cancer detection and treatment by nanobots. This includes a feasible and precise model of agent locomotion, which is inspired by actual nanoscopic vesicles which, when in the presence of an external chemical gradient, tend towards areas of higher concentration by means of self-propulsion. The delivered payloads have a dual purpose of treating the cancer, as well as diffusing throughout the space to form a chemical gradient which other agents can sense and noisily ascend. We present simulation results to analyze the behavior of individual agents under our locomotion model and to investigate the efficacy of this collectively amplified chemical signal in helping the larger swarm efficiently locate the cancer site. 

Task allocation is an important problem for robot swarms to solve, allowing agents to reduce task completion time by performing tasks in a distributed fashion. Existing task allocation algorithms often assume prior knowledge of task location and demand or fail to consider the effects of the geometric distribution of tasks on the completion time and communication cost of the algorithms. In this paper, we examine an environment where agents must explore and discover tasks with positive demand and successfully assign themselves to complete all such tasks. We first provide a new discrete general model for modeling swarms. Operating within this theoretical framework, we propose two new task allocation algorithms for initially unknown environments – one based on N-site selection and the other on virtual pheromones. We analyze each algorithm separately and also evaluate the effectiveness of the two algorithms in dense vs. sparse task distributions. Compared to the Levy walk, which has been theorized to be optimal for foraging, our virtual pheromone inspired algorithm is much faster in sparse to medium task densities but is communication and agent intensive. Our site selection inspired algorithm also outperforms Levy walk in sparse task densities and is a less resource-intensive option than our virtual pheromone algorithm for this case. Because the performance of both algorithms relative to random walk is dependent on task density, our results shed light on how task density is important in choosing a task allocation algorithm in initially unknown environments. 

Due to the increasing complexity of robot swarm algorithms, ana- lyzing their performance theoretically is often very difficult. Instead, simulators are often used to benchmark the performance of robot swarm algorithms. However, we are not aware of simulators that take advantage of the naturally highly parallel nature of distributed robot swarms. This paper presents ParSwarm, a parallel C++ frame- work for simulating robot swarms at scale on multicore machines. We demonstrate the power of ParSwarm by implementing two applications, task allocation and density estimation, and running simulations on large numbers of agents. 

Task allocation is an important problem for robot swarms to solve, allowing agents to reduce task completion time by performing tasks in a distributed fashion. Existing task allocation algorithms often assume prior knowledge of task location and demand or fail to consider the effects of the geometric distribution of tasks on the completion time and communication cost of the algorithms. In this paper, we examine an environment where agents must explore and discover tasks with positive demand and successfully assign themselves to complete all such tasks. We first provide a new dis- crete general model for modeling swarms. Operating within this theoretical framework, we propose two new task allocation algo- rithms for initially unknown environments – one based on N-site selection and the other on virtual pheromones. We analyze each algorithm separately and also evaluate the effectiveness of the two algorithms in dense vs. sparse task distributions. Compared to the Levy walk, which has been theorized to be optimal for foraging, our virtual pheromone inspired algorithm is much faster in sparse to medium task densities but is communication and agent intensive. Our site selection inspired algorithm also outperforms Levy walk in sparse task densities and is a less resource-intensive option than our virtual pheromone algorithm for this case. Because the perfor- mance of both algorithms relative to random walk is dependent on task density, our results shed light on how task density is impor- tant in choosing a task allocation algorithm in initially unknown environments.